1. Field of the Invention
This invention relates to computer systems, and more particularly to mechanisms for determining and selecting among routes across nodes in a network.
2. Description of the Related Art
A common solution for mesh routing in Wireless Sensor Networks (WSNs) involves an Ad-Hoc On-Demand Distance Vector (AODV) based routing algorithm. FIGS. 1A and 1B illustrate prior art calculation of a route according to the AODV model. In the AODV model, routes are calculated based on the number of hops between the source and destination nodes. The resulting route is most commonly accepted to be that which includes the shortest number of hops between nodes. In FIG. 1A, in the AODV model, to find a route to a destination node D, a source node S floods the network with a route request. Each node that receives the route request forwards the route request to neighboring nodes that it knows about. When the destination node D receives the route requests from one or more nodes, the destination node D returns at least one route reply on the network. When the source node S receives two or more route replies, it selects a route based on the shortest route as determined by the number of hops, as illustrated in FIG. 1B. Thus, the route selection metric in AODV is the number of hops.
The AODV routing solution suffers from a number of problems in the WSN space. For example, paths with the shortest number of hops may result in traversing less stable links. Within a wireless network, the most direct route may involve radio communications over longer distances. With the variability of radio communications at longer distances, the result is that shortest path routes may fail often and thus may require a new route to be calculated frequently. As another example, nodes in a WSN often have finite power supplies, such as batteries, which may have effects on routing. For example, the frequency of route discovery and calculation may deplete power across all potential nodes in the path. In addition, the utility of the overall mesh network may be dependent on a small number of routing nodes. If a single node is totally depleted, it may render all or part of the mesh unreachable.